package com.leetcode.algorithm.y22.m08.w3;

import java.util.ArrayDeque;
import java.util.Deque;

import com.leetcode.algorithm.common.TreeNode;

/**
 * 236. 二叉树的最近公共祖先
 * 
 * https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/
 * 
 * @author jie.deng
 *
 */
class Question0236Solution01 {

	public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
		Deque<TreeNode> pathP = new ArrayDeque<>();
		findPath(root, p, pathP);
		Deque<TreeNode> pathQ = new ArrayDeque<>();
		findPath(root, q, pathQ);

		if (pathP.size() >= pathQ.size()) {
			int cnt = pathP.size() - pathQ.size();
			while (cnt > 0) {
				pathP.pollLast();
				cnt--;
			}
		} else {
			int cnt = pathQ.size() - pathP.size();
			while (cnt > 0) {
				pathQ.pollLast();
				cnt--;
			}
		}
		while (!pathP.isEmpty() && pathP.peekLast() != pathQ.peekLast()) {
			pathP.pollLast();
			pathQ.pollLast();
		}
		return pathP.peekLast();
	}

	private void findPath(TreeNode cur, TreeNode target, Deque<TreeNode> path) {
		path.offerLast(cur);
		if (cur == target) {
			return;
		}
		if (cur.left != null) {
			findPath(cur.left, target, path);
			if (path.peekLast() == target) {
				return;
			}
		}
		if (cur.right != null) {
			findPath(cur.right, target, path);
			if (path.peekLast() == target) {
				return;
			}
		}
		path.pollLast();
	}

}